Polar codes are capacity achieving codes that have received a significant amount of attention recently, and are being considered as a specification for channel codes in fifth generation (5G) communication systems. Polar codes are also being considered for error correcting codes in memory systems.
Polar codes are classically decoded with a successive cancellation decoder (SCD) which has a computational complexity on the order of (N log N) for a code of length N, where N is an integer. However, the serial nature of an SCD also results in a large decoding latency of (N log N), where N is a code length. The SCD decoding latency can be reduced to 2N−2, using multidimensional polar decoding where multiplicities of each node at the decoding tree are decoded in parallel. Better decoding performance may be achieved by list decoding polar codes. However, list decoding of a polar code has a computational complexity on the order of O(LN log N) for a list size of L, which is an L-fold increase over that of successive cancellation decoding of a polar code.